package common.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 原理:
 * 先以个位进行排序，然后以十位、百位等依次进行排序
 * 排到最后就是一个有序数组
 */
public class RadixSort02 implements Sort {

    @Override
    public void sort(int[] array) {
        int maxNumLength = getMaxLength(getMaxNum(array));
        radixSort(array, maxNumLength);
    }

    void radixSort(int[] array, int maxNumLength) {
        //创建10个桶
        List<List<Integer>> bucketList = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<>());
        }

        // 从个位开始排序
        for (int i = 0; i < maxNumLength; i++) {

            for (int j = 0; j < array.length; j++) {
                int bucket = (array[j] / (int) Math.pow(10, i)) % 10;
                bucketList.get(bucket).add(array[j]);
            }

            // 合并发原数组
            int pos = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int t : bucketList.get(j)) {
                    array[pos++] = t;
                }
                bucketList.get(j).clear();
            }
        }
    }

    int getMaxNum(int[] array) {
        int m = array[0];
        for (int t : array) {
            if (t > m) {
                m = t;
            }
        }
        return m;
    }

    int getMaxLength(int n) {
        if (n == 0) {
            return 1;
        }
        int r = 0;
        while (n > 0) {
            n = n / 10;
            r++;
        }
        return r;
    }
}
